package stack;

/**
 * 中缀表达式的计算器(加入小括号)
 * 如何将中缀表达式转为中缀表达式树
 * @Auther Jun jie Yi
 * @Date 22:54 2021/7/6
 */
public class Calculator1 {
    public static void main(String[] args) {
        String expression = "23+(2+5+1)*(3+5)";
        //数栈
        ArrayStack numStack = new Calculator1().new ArrayStack(10);
        //符号栈
        ArrayStack operateStack = new Calculator1().new ArrayStack(10);
        //用于扫描
        int index = 0;
        int num1 = 0;
        int num2 = 0;
        int operate = 0;
        int res = 0;
        char ch = ' '; //将每次扫描得到的char保存到ch
        String keepNum = ""; //用于拼接多位数
        while(index < expression.length()) {
            ch = expression.charAt(index);
            //判断是否是运算符
            if(operateStack.isOperate(ch)){
                //判断当的符号栈是否为空
                if(!operateStack.isEmpty()) {
                    //如果遇到了 ')' 符号，就将 '(', ')' 包裹的所有符号运算出
                    if(ch == ')') {
                        while(operateStack.peek() != '(') {
                            num1 = numStack.pop();
                            num2 = numStack.pop();
                            operate = operateStack.pop();
                            res = numStack.cal(num1, num2, operate);
                            numStack.push(res);
                        }
                        //将符号 '(' 进行出栈
                        operateStack.pop();
                        index ++;
                        continue;
                    }
                    //如果符号栈有操纵符，就进行比较，如果当前的的操作符的优先级<=栈中的操作符
                    //就需要从数栈中pop出两个数。在从符号栈中pop出一个符号，进行运算，将的到结果，入数栈然后将当前的操作符入符号栈
                    if(operateStack.priority(ch) <= operateStack.priority(operateStack.peek()) && operateStack.peek() != '(') {
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        operate = operateStack.pop();
                        res = numStack.cal(num1, num2, operate);
                        //把运算的结果入数栈
                        numStack.push(res);
                    }
                }
                //将当前运算符入栈
                operateStack.push(ch);
            } else {
                //如果是数就直接入数栈
                //numStack.push(ch - 48);

                //分析思路
                //1.当处理多位数时，不能发现一个数就立即入栈，因为他可能是多位数
                //2.在处理数，需要向expression的表达式的index后再看一位，如果是数就进行扫描，如果是符号才入栈
                //3.因此我们需要定义一个字符串变量进行拼接
                keepNum += ch;
                //如果ch已经是expression的最后一位，就直接入栈(这里不写会爆越界错误)
                if(index == expression.length() - 1) {
                    numStack.push(Integer.parseInt(keepNum));
                } else {
                    //判断下一个字符是否是操作符，如果是数字就继续扫描，如果是运算符则入栈
                    if(operateStack.isOperate(expression.charAt(index + 1))) {
                        numStack.push(Integer.parseInt(keepNum));
                        keepNum = "";
                    }
                }
            }
            index ++;
        }

        //当表达式扫描完毕后，就顺序的从符号栈中pop出相应的数和符号，并运行
        while(!operateStack.isEmpty()) {
            //如果符号栈为空，则计算到最后的结果，数栈中只有一个数字（结果）
            num1 = numStack.pop();
            num2 = numStack.pop();
            operate = operateStack.pop();
            res = numStack.cal(num1, num2, operate);
            numStack.push(res);
        }
        System.out.printf("表达式%s=%d", expression, numStack.pop());
    }

    //定义这个类表示栈结构 ----------------------------------------------------------
    class ArrayStack{
        private int maxSize; //栈的大小
        private int[] stack; //数组，这里用数组模拟栈
        private int top = -1; //没有数据时，初始化栈顶下标为 -1
        //构造器
        public ArrayStack(int maxSize) {
            this.maxSize = maxSize;
            stack = new int[this.maxSize];
        }
        //栈满
        public boolean isFull() {
            return top == maxSize - 1;
        }
        //栈空
        public boolean isEmpty() {
            return top == -1;
        }
        //入栈 push
        public void push(int value) {
            //判断栈是否已经满了
            if(isFull()) {
                System.out.println("栈满");
            } else {
                stack[++ top] = value;
            }
        }
        //出栈 pop
        public int pop() {
            //判断栈是否已经满了
            if(isEmpty()) {
                throw new RuntimeException("栈为空");
            } else {
                int value = stack[top];
                top --;
                return value;
            }
        }
        //返回栈顶的值
        public int peek() {
            return stack[top];
        }
        //遍历整个栈
        public void list() {
            if(isEmpty()) {
                System.out.println("栈空，无法遍历");
                return;
            } else {
                //需要从栈顶开始显示数据
                for (int i = top; i >= 0; i--) {
                    System.out.printf("stack[%d]=%d\n", i, stack[i]);
                }
            }
        }
        //数字越大，优先级越高
        public int priority(int operate) {
            if(operate == '(') {
                return 2;
            } else if(operate == '*' || operate == '/') {
                return 1;
            }else if(operate == '+' || operate == '-') {
                return 0;
            } else {
                return -1; //默认现在的表达式只有 +、-、*、/ 还没有 ()
            }
        }
        //判断是否是一个运算符
        public boolean isOperate(char val) {
            return val == '+' || val == '-' || val == '*' || val == '/' || val == '(' || val == ')';
        }
        //计算方法
        public int cal(int num1, int num2, int operate) {
            int res = 0; //res 用于存放计算的结果
            switch(operate) {
                case '+':
                    res = num1 + num2;
                    break;
                case '-':
                    res = num2 - num1;
                    break;
                case '*':
                    res = num1 * num2;
                    break;
                case '/':
                    res = num2 / num1;
                    break;
                default:
                    break;
            }
            return res;
        }
    }
}
